package interview.algorithms.again_in_interview;

import common.ListNode;
import common.TreeNode;

import java.util.*;

/**
 * @author fance
 * @date 2018/8/1 16:40
 */
public class SumI {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    public int binarySearch(int[] arr, int target) {
        int lo = 0;
        int hi = arr.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] > target) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return -1;
    }

    /**
     * 104. 二叉树的最大深度
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
    }

    /**
     * 46. 全排列
     * @param nums
     * @return
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length < 1) {
            return res;
        }
        permuteCore(nums,0,res);
        return res;
    }
    private void permuteCore(int[] nums, int index, List<List<Integer>> res) {
        if (index == nums.length - 1) {
            List<Integer> tmpList = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                tmpList.add(nums[i]);
            }
            res.add(tmpList);
        } else if (index < nums.length - 1) {
            for (int i = index; i <  nums.length; i++) {
                int tmp = nums[i];
                nums[i] = nums[index];
                nums[index] = tmp;

                permuteCore(nums, index + 1, res);

                 tmp = nums[i];
                nums[i] = nums[index];
                nums[index] = tmp;
            }
        }
    }

    public List<List<Integer>> permuteII(int[] nums){
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        backtrackForpermuteII(res,new ArrayList<>(), nums);
        return res;
    }
    private void backtrackForpermuteII(List<List<Integer>> res, List<Integer> tmpList, int [] nums) {
        if (tmpList.size() == nums.length) {
            res.add(new ArrayList<>(tmpList));
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (tmpList.contains(nums[i])) {
                    continue;
                }
                tmpList.add(nums[i]);
                backtrackForpermuteII(res,tmpList,nums);
                tmpList.remove(tmpList.size() - 1);
            }
        }
    }

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length < 3) {
            return res;
        }
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int j = i + 1;
            int k = n - 1;
            int target = -nums[i];
            while (j < k) {
                if (nums[j] + nums[k] == target) {
                    List<Integer> tmp = new ArrayList<>();
                    tmp.add(nums[i]);
                    tmp.add(nums[j]);
                    tmp.add(nums[k]);
                    j++;
                    k--;
                    res.add(tmp);

                    while (j < k && nums[j] == nums[j - 1]) {
                        j++;
                    }
                    while (j < k && nums[k] == nums[k + 1]) {
                        k--;
                    }
                }else if (nums[j] + nums[k] < target) {
                    j++;
                } else {
                    k--;
                }
            }
        }
        return res;
    }

    /**
     * 1. Two Sum
     * 1.bf 2.排序 双指针 3.hashmap记录
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSumI(int[] nums, int target) {
        int[] res = new int[2];
        Arrays.sort(nums);
        int i = 0;
        int j = nums.length - 1;
        int cur;
        while (i < j) {
            cur = nums[i] + nums[j];
            if (cur == target) {
                res[0] = i;
                res[1] = j;
                return res;
            } else if (cur > target) {
                j--;
            } else {
                i++;
            }
        }
        return res;
    }

    public int[] twoSumII(int[] nums, int target) {
        int[] res = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {

            if (map.containsKey(nums[i])) {
                res[0] = map.get(nums[i]);
                res[1] = i;
                return res;
            } else {
                map.put(target - nums[i],i);
            }
        }
        return res;
    }


    public ArrayList<Integer> postOrderUnRecur(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        LinkedList<TreeNode> stack1 = new LinkedList<>();
        LinkedList<TreeNode> stack2 = new LinkedList<>();
        stack1.push(root);
        while (stack1.isEmpty() == false) {
            root = stack1.pop();
            stack2.push(root);

            if (root.left != null) {
                stack1.push(root.left);
            }
            if (root.right != null) {
                stack1.push(root.right);
            }
        }
        while (stack2.isEmpty() == false) {
            res.add(stack2.pop().val);
        }
        return res;
    }

    public int sumNumbers(TreeNode root) {
        return sumNumbersCore(root,0);
    }
    public int sumNumbersCore(TreeNode root,int sum) {
        if (root == null) {
            return 0;
        }
        sum = sum * 10 + root.val;
        if (root.left == null && root.right == null) {
            return sum;
        }
        return sumNumbersCore(root.left,sum) + sumNumbersCore(root.right,sum);
    }

    int maxValue;
    public int maxPathSum(TreeNode root) {
        maxValue = Integer.MIN_VALUE;
        maxPathDown(root);
        return maxValue;
    }
    private int maxPathDown(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = Math.max(0,maxPathDown(node.left));
        int right = Math.max(0,maxPathDown(node.right));
        maxValue = Math.max(maxValue,left + right + node.val);
        return Math.max(left,right) + node.val;
    }

}
